//
// Description: 5186. 区间内查询数字的频率
// Created by Loading on 2021/11/21.
//

#include <bits/stdc++.h>

using namespace std;

class RangeFreqQuery {
public:
    explicit RangeFreqQuery(vector<int> &arr) {
        for (int i = 0; i < arr.size(); ++i) {
            m[arr[i]].emplace_back(i);
        }
    }

    int query(int left, int right, int value) {
        if (m.find(value) == m.end()) {
            return 0;
        }
        // 二分查找
        auto r = upper_bound(m[value].begin(), m[value].end(), right);
        auto l = lower_bound(m[value].begin(), m[value].end(), left);
        return r - l;
    }

private:
    unordered_map<int, vector<int>> m;
};

int main() {
    vector<int> arr = {12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56};
    RangeFreqQuery rangeFreqQuery(arr);
    int query1 = rangeFreqQuery.query(1, 2, 4);
    int query2 = rangeFreqQuery.query(0, 11, 33);
    cout << query1 << endl;
    cout << query2 << endl;

    return 0;
}